package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/27 0027.
 */
public class Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal {
    int curPreIdx = 0;
    private boolean build(int[] preorder, TreeNode root, List<Integer> subLeft, List<Integer> subRight){
        if(curPreIdx<preorder.length){
            boolean rst = false;
            if(!rst){
                int nxt = preorder[curPreIdx];
                TreeNode cur = new TreeNode(nxt);
                if(subLeft.contains(nxt)){
                    curPreIdx++;
                    root.left = cur;
                    int sepIdx = subLeft.indexOf(nxt);
                    List<Integer> Left = subLeft.subList(0,sepIdx);
                    List<Integer> Right = subLeft.subList(sepIdx+1,subLeft.size());
                    rst = build(preorder, cur, Left, Right);
                }
            }
            if(!rst){
                int nxt = preorder[curPreIdx];
                TreeNode cur = new TreeNode(nxt);
                if(subRight.contains(nxt)){
                    curPreIdx++;
                    root.right = cur;
                    int sepIdx = subRight.indexOf(nxt);
                    List<Integer> Left = subRight.subList(0,sepIdx);
                    List<Integer> Right = subRight.subList(sepIdx+1,subRight.size());
                    rst = build(preorder,cur,Left, Right);
                }
            }
            return rst;
        }
        return true;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null || inorder== null || preorder.length==0 || inorder.length==0)
            return null;
        ArrayList<Integer> inOrder = new ArrayList<Integer>(inorder.length);
        for(Integer integer:inorder)
            inOrder.add(integer);
        TreeNode root = new TreeNode(preorder[curPreIdx]);
        int sepIdx = inOrder.indexOf(preorder[curPreIdx]);
        List<Integer> subLeft = inOrder.subList(0,sepIdx);
        List<Integer> subRight = inOrder.subList(sepIdx+1,inOrder.size());
        curPreIdx = 1;
        build(preorder, root, subLeft, subRight);
        return root;
    }
    public static void main(String[] args){
        Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal construct_binary_tree_from_preorder_and_inorder_traversal = new Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal();
        int[] pre = {1};
        int[] in = {1};
        TreeNode root = construct_binary_tree_from_preorder_and_inorder_traversal.buildTree(pre,in);
        System.out.println(root);
    }
}
